#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stddef.h>
#include "klist.h"

// 哈希表大小，选择一个质数可以减少冲突
#define HASHTABLE_SIZE 1021

// 单词节点结构
struct word_node {
	char *word; // 单词
	int count;  // 出现次数
	struct hlist_node hnode; // 哈希表节点
};

// 哈希表结构
struct word_hashtable {
	struct hlist_head buckets[HASHTABLE_SIZE]; // 哈希桶数组
};

// 计算字符串的哈希值(djb2算法)
static unsigned int hash_str(const char *str)
{
	unsigned int hash = 5381;
	int c;

	while ((c = *str++)) {
		hash = ((hash << 5) + hash) + c; // hash * 33 + c
	}

	return hash % HASHTABLE_SIZE;
}

// 初始化哈希表
void hashtable_init(struct word_hashtable *ht)
{
	for (int i = 0; i < HASHTABLE_SIZE; i++) {
		INIT_HLIST_HEAD(&ht->buckets[i]);
	}
}

// 在哈希表中查找或插入单词
struct word_node *hashtable_insert(struct word_hashtable *ht, const char *word)
{
	// 复制单词字符串(转换为小写存储)
	char *word_copy = strdup(word);
	if (!word_copy) {
		perror("strdup failed");
		exit(EXIT_FAILURE);
	}
	#if 0
		// 转换为小写
		for (char *p = word_copy; *p; p++) {
			*p = tolower(*p); // 转换为小写
		}
	#endif

	// 计算哈希值确定桶位置
	unsigned int bucket = hash_str(word_copy);
	struct hlist_head *head = &ht->buckets[bucket];
	

	// 在链表中查找是否已存在该单词（不区分大小写）
	
	struct word_node *node;
	hlist_for_each_entry(node, head, hnode) {
		if (strcasecmp(node->word, word_copy) == 0) {
			// 找到匹配，增加计数并返回
			node->count++;
			if (word_copy)
				free(word_copy);
			return node;
		}
	}

	// 没找到，创建新节点
	node = malloc(sizeof(struct word_node));
	if (!node) {
		perror("malloc failed");
		if (word_copy)
			free(word_copy);
		exit(EXIT_FAILURE);
	}

	node->word = word_copy;
	node->count = 1;
	
	// 初始化哈希表节点
	INIT_HLIST_NODE(&node->hnode);

	// 插入到链表头部
	hlist_add_head(&node->hnode, head);

	return node;
}

// 释放哈希表内存
void hashtable_free(struct word_hashtable *ht)
{
	for (int i = 0; i < HASHTABLE_SIZE; i++) {
		struct hlist_head *head = &ht->buckets[i];
		struct hlist_node *tmp;
		struct word_node *node;

		hlist_for_each_entry_safe(node, tmp, head, hnode) {
			hlist_del(&node->hnode);
			free(node->word);
			free(node);
		}
	}
}

// 比较函数，用于排序（按计数降序）
int compare_nodes(const void *a, const void *b)
{
	struct word_node *node_a = *(struct word_node **)a;
	struct word_node *node_b = *(struct word_node **)b;

	// 先按计数降序
	if (node_a->count != node_b->count) {
		return node_b->count - node_a->count; // 降序
	}

	// 计数相同，按字母升序
	return strcmp(node_a->word, node_b->word); // 升序
}

// 从文件中读取单词并统计
void process_file(struct word_hashtable *ht, FILE *file)
{
	int c;
	char word[256];
	int pos = 0;

	while ((c = fgetc(file)) != EOF) {
		if (isalpha(c) || c == '\'' ) {
			// 字母字符，添加到当前单词
			if (pos < sizeof(word) - 1) {
				word[pos++] = c;
			}
		} else if (pos > 0) {
			// 非字母字符，且当前有单词，则处理单词
			word[pos] = '\0';
			hashtable_insert(ht, word);
			pos = 0;
		}
	}

	// 处理最后一个单词（如果有）
	if (pos > 0) {
		word[pos] = '\0';
		hashtable_insert(ht, word);
	}
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
		return EXIT_FAILURE;
	}

	FILE *file = fopen(argv[1], "r");
	if (!file) {
		perror("fopen failed");
		return EXIT_FAILURE;
	}

	// 初始化哈希表
	struct word_hashtable ht;
	hashtable_init(&ht);

	// 处理文件
	process_file(&ht, file);
	fclose(file);

	// 收集所有节点到数组
	int node_count = 0;

	for (int i = 0; i < HASHTABLE_SIZE; i++) {
		struct hlist_head *head = &ht.buckets[i];
		struct word_node *node;

		hlist_for_each_entry(node, head, hnode) {
			node_count++;
		}
	}

	// 分配数组空间
	struct word_node **nodes = malloc(node_count * sizeof(struct word_node *));
	if (!nodes) {
		perror("malloc failed");
		return EXIT_FAILURE;
	}

	// 填充数组
	int index = 0;
	for (int i = 0; i < HASHTABLE_SIZE; i++) {
		struct hlist_head *head = &ht.buckets[i];
		struct word_node *node;

		hlist_for_each_entry(node, head, hnode) {
			nodes[index++] = node;
		}
	}

	// 按计数排序
	qsort(nodes, node_count, sizeof(struct word_node *), compare_nodes);

	// 打印结果
	printf("The number of word is %d\n", node_count);
	printf("%-20s %s\n", "Word", "Count");
	printf("-------------------- ------\n");
	for (int i = 0; i < node_count; i++) {
		printf("%-20s %d\n", nodes[i]->word, nodes[i]->count);
	}

	// 释放内存
	free(nodes);
	hashtable_free(&ht);

	return EXIT_SUCCESS;
}